package baseclass.m_graph;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @date 2020/3/6 22:15
 */
public class Code05_Prim {
    public static Set<Edge> prim(Node node){
        //存放已经被解锁的点
        Set<Node> visitedSet = new HashSet<>();
        //小根堆，存放已经解锁的点的所有边。
        PriorityQueue<Edge> weightQueue =
                new PriorityQueue<>((e1,e2) -> e1.weight - e2.weight);
        //返回边
        Set<Edge> res = new HashSet<>();
        //从任意一个点出发
        if(!visitedSet.contains(node)){
            //加入到set，表示该点已经被解锁，并把所有与其关联的边【指的是从node出发的边】放入小根堆
            visitedSet.add(node);
            for (Edge edge : node.edges) {
                weightQueue.offer(edge);
            }
            while (!weightQueue.isEmpty()){
                //弹出最短权值的边
                Edge edge = weightQueue.poll();
                //拿到其终止节点
                Node toNode = edge.to;
                //如果终止节点未被解锁，则解锁
                if (!visitedSet.contains(toNode)) {
                    visitedSet.add(toNode);
                    //把这条边放入res，并遍历这个toNode的所有边，放入小根堆
                    res.add(edge);
                    for (Edge nextEdge : toNode.edges) {
                        weightQueue.add(nextEdge);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Integer[][]matrix = {{1,1,2},{2,1,3},{2,1,4},{1,2,3},{3,2,4},{4,3,4}};
        Graph graph = Graph.createGraph(matrix);
        Set<Edge> edges = prim(graph.nodes.get(1));
        for (Edge edge : edges) {
            System.out.println(edge.from.val+"->"+edge.to.val+" 权重:"+edge.weight);
        }
    }

}
